#include "rbtree.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "queue.h"

#define true 1
#define false 0
/*************************静态函数前置声明****************************/
/*判断树是否为空*/
static int checkRbtree(Rbtree *rbtree);
/*判断树结点是否为空*/
static int checkRbtreeNode(RbtreeNode *node);
/*寻找前驱结点*/
static RbtreeNode *seekPreNode(Rbtree *rbtree, RbtreeNode *node);
/*寻找后继结点*/
static RbtreeNode *seekPostNode(Rbtree *rbtree, RbtreeNode *node);
/*判断结点是否度为2*/
static int nodeDegreeIsTwo(Rbtree *rbtree, RbtreeNode *node);
/*判断结点是否度为1*/
static int nodeDegreeIsOne(Rbtree *rbtree, RbtreeNode *node);
/*判断结点是否度为0*/
static int nodeDegreeIsZero(Rbtree *rbtree, RbtreeNode *node);
/*前序遍历*/
static int prePrint(Rbtree *rbtree, RbtreeNode *node);
/*中序遍历*/
static int inOrderPrint(Rbtree *rbtree, RbtreeNode *node);
/*后序遍历*/
static int postPrint(Rbtree *rbtree, RbtreeNode *node);
/*左旋*/
static int leftRotate(Rbtree *rbtree, RbtreeNode *grand);
/*右旋*/
static int rightRotate(Rbtree *rbtree, RbtreeNode *grand);
/*插入后调整*/
static int insertFixup(Rbtree *rbtree, RbtreeNode *node);
/*删除后调整*/
static int deleteFixup(Rbtree *rbtree, RbtreeNode *node);
/*************************静态函数前置实现****************************/
static int checkRbtree(Rbtree *rbtree)
{
    if (rbtree == NULL)
    {
        return NULL_TREE;
    }
}
static int checkRbtreeNode(RbtreeNode *node)
{
    if (node == NULL)
    {
        return NULL_NODE;
    }
}
/*寻找前驱结点*/
/*寻找前驱结点的算法:
如果当前结点有左子树就寻找左子树的最右孩子
如果没有左子树就寻找第一个左父结点*/
static RbtreeNode *seekPreNode(Rbtree *rbtree, RbtreeNode *node)
{
    /*左子树不为空*/
    if (node->left != rbtree->leaf)
    {
        node = node->left;
        /*寻找最右子树*/
        while (node->right != rbtree->leaf)
        {
            node = node->right;
        }
        return node;
    }
    else
    {
        /*左子树为空：寻找第一个右父结点*/
        /*如果当前结点是左孩子，一直向父节点遍历*/
        while (node->parent != rbtree->leaf && node == node->parent->left)
        {
            node = node->parent;
        }
        /*只要当前不为左孩子,父节点即是前驱节点*/
        if (node->parent == rbtree->leaf)
        {
            return NULL;
        }
        return node->parent;
    }
}
/*寻找后继结点*/
/*寻找前驱结点的算法:
如果当前结点有右子树就寻找右子树的最左孩子
如果没有左子树就寻找第一个右父结点*/
static RbtreeNode *seekPostNode(Rbtree *rbtree, RbtreeNode *node)
{
    /*右子树不为空*/
    if (node->right != rbtree->leaf)
    {
        node = node->right;
        /*寻找最左子树*/
        while (node->left != rbtree->leaf)
        {
            node = node->left;
        }
        return node;
    }
    else
    {
        /*右子树为空：寻找第一个左父结点*/
        /*如果当前结点是右孩子，一直向父节点遍历*/
        while (node->parent != rbtree->leaf && node == node->parent->right)
        {
            node = node->parent;
        }
        /*只要当前不为右孩子,父节点即是后继节点*/
        if (node->parent == rbtree->leaf)
        {
            return NULL;
        }
        return node->parent;
    }
}
/*判断结点是否度为2*/
static int nodeDegreeIsTwo(Rbtree *rbtree, RbtreeNode *node)
{
    return (node->left != rbtree->leaf && node->right != rbtree->leaf) ? true : false;
}
/*判断结点是否度为1*/
static int nodeDegreeIsOne(Rbtree *rbtree, RbtreeNode *node)
{
    return (node->left != rbtree->leaf && node->right == rbtree->leaf) || (node->left == rbtree->leaf && node->right != NULL) ? true : false;
}
/*判断结点是否度为0*/
static int nodeDegreeIsZero(Rbtree *rbtree, RbtreeNode *node)
{
    return (node->left == rbtree->leaf && node->right == rbtree->leaf) ? true : false;
}
static int prePrint(Rbtree *rbtree, RbtreeNode *node)
{
    if (node == rbtree->leaf)
    {
        return ON_SUCCESS;
    }
    rbtree->printTree(node->val);
    prePrint(rbtree, node->left);
    prePrint(rbtree, node->right);
}
static int inOrderPrint(Rbtree *rbtree, RbtreeNode *node)
{
    if (node == rbtree->leaf)
    {
        return ON_SUCCESS;
    }
    prePrint(rbtree, node->left);
    rbtree->printTree(node->val);
    prePrint(rbtree, node->right);
}
static int postPrint(Rbtree *rbtree, RbtreeNode *node)
{
    if (node == rbtree->leaf)
    {
        return ON_SUCCESS;
    }
    prePrint(rbtree, node->left);
    prePrint(rbtree, node->right);
    rbtree->printTree(node->val);
}
static int leftRotate(Rbtree *rbtree, RbtreeNode *grand)
{
    RbtreeNode *parent = grand->right;
    RbtreeNode *child = parent->left;

    parent->left = grand; // 1

    grand->right = child; // 2

    parent->parent = grand->parent; // 3

    if (grand->parent == rbtree->leaf)
    {
        rbtree->root = parent;
    }
    else
    {
        if (grand == grand->parent->left)
        {
            grand->parent->left = parent; // 4
        }
        else
        {
            grand->parent->right = parent;
        }
    }

    grand->parent = parent; // 5
    if (child != rbtree->leaf)
    {
        child->parent = grand; // 6
    }

    return ON_SUCCESS;
}
static int rightRotate(Rbtree *rbtree, RbtreeNode *grand)
{
    RbtreeNode *parent = grand->left;
    RbtreeNode *child = parent->right;

    parent->right = grand; // 1
    grand->left = child;   // 2

    parent->parent = grand->parent; // 3
    if (grand->parent == rbtree->leaf)
    {
        rbtree->root = parent;
    }
    else
    {
        if (grand == grand->parent->left)
        {
            grand->parent->left = parent; // 4
        }
        else
        {
            grand->parent->right = parent;
        }
    }

    grand->parent = parent; // 5
    if (child != rbtree->leaf)
    {
        child->parent = grand; // 6
    }
    return ON_SUCCESS;
}
static int insertFixup(Rbtree *rbtree, RbtreeNode *node)
{
    if (rbtree == NULL)
    {
        return NULL_TREE;
    }

    /*不考虑节点的父节点或者祖父节点为空吗*/
    while (node->parent->color == RED)
    {
        if (node->parent == node->parent->parent->left)
        {

            /*当前子树是祖父结点的左子树,L情况*/
            /*当前结点的叔叔：父节点的兄弟*/
            RbtreeNode *uncle = node->parent->parent->right;
            if (uncle->color == RED)
            {
                /*父红叔红：变色即可,父变黑，叔也变黑，祖父变红*/
                uncle->color = BLACK;
                node->parent->color = BLACK;
                node->parent->parent->color = RED;
                /*转移到组父节点继续向上判断*/
                node = node->parent->parent;
            }
            else
            {
                /*父红叔黑:1.判断RR，RL，LL，LR的情况*/
                if (node->parent->right == node)
                {
                    /*LR:先左旋，再右旋*/
                    /*先让父节点作为根基旋转*/
                    leftRotate(rbtree, node->parent);
                }
                /*LL:直接右旋*/
                /*祖父结点和父节点变色*/
                node->parent->color = BLACK;
                node->parent->parent->color = RED;
                /*再让祖父节点作为根基旋转*/
                rightRotate(rbtree, node->parent->parent);
            }
        }
        else
        {
            /*父节点是祖父节点的右子树,R情况*/
            /*上面程序的对称版本*/
            RbtreeNode *uncle = node->parent->parent->left;
            if (uncle->color == RED)
            {
                /*祖父变红，父叔由红变黑*/
                uncle->color = BLACK;
                node->parent->color = BLACK;
                node->parent->parent->color = RED;
                node = node->parent->parent;
            }
            else
            {
                /*父红叔黑*/
                if (node == node->parent->left)
                {
                    /*是否要把node=node->parent*/
                    /*RL:先右旋再左旋*/
                    rightRotate(rbtree, node->parent);
                }
                /*RR:直接左旋*/
                node->parent->color = BLACK;
                node->parent->parent->color = RED;
                leftRotate(rbtree, node->parent->parent);
            }
        }
    }
    rbtree->root->color = BLACK;
    return ON_SUCCESS;
}
int deleteFixup(Rbtree *rbtree, RbtreeNode *node)
{
    while (node->color == BLACK && node != rbtree->root)
    {
        if (node == node->parent->left)
        /*node作为父节点的左子树*/
        /*      parent
               /     \
             node   brother
       */
        { /*定义兄弟节点*/
            RbtreeNode *brother = node->parent->right;
            if (brother->color == RED)
            {
                /*左节点为红，右兄弟为红，父节点必为黑*/
                /*兄弟和父亲变色*/
                brother->color = BLACK;
                node->parent->color = RED;
                /*左旋*/
                leftRotate(rbtree, node->parent);
                /*将brother结点更新为node的新右兄弟*/
                brother = node->parent->right;
            }
            /*到这里兄弟颜色一定为黑色*/
            if (brother->left->color == BLACK && brother->right->color == BLACK)
            {
                /*兄黑双侄子黑*/
                /*兄弟黑变红，父亲由红变黑*/
                /*若父亲本来颜色就是黑色，node指向父亲循环调整*/
                brother->color = RED;
                node = node->parent;
                /*...进下一次循环：本身黑色就继续判断，红色就结束*/
            }
            else
            {
                /*侄子由红的：判断是顺侄红还是对侄红*/
                if (brother->right->color == BLACK)
                {
                    /*右侄子为黑，左侄子红，即顺侄红情况*/
                    brother->left->color = BLACK;
                    brother->color = RED;
                    rightRotate(rbtree, brother);
                    brother = node->parent->right;
                }
                /*顺侄红转化为对侄红*/
                /*对侄红*/
                /*兄弟颜色变为父亲颜色*/
                brother->color = node->parent->color;
                /*父亲颜色变黑*/
                node->parent->color = BLACK;
                brother->right->color = BLACK;
                leftRotate(rbtree, node->parent);

                /*退出循环*/
                node = rbtree->root;
            }
        }
        else
        {
            /*      parent
                   /     \
                brother     node
            */
            /*node作为父节点的右子树*/
            RbtreeNode *brother = node->parent->left;
            if (brother->color == RED)
            {
                /*兄红*/
                brother->color = BLACK;
                node->parent->color = RED;
                rightRotate(rbtree, node->parent);
                brother = node->parent->left;
            }
            if (brother->left->color == BLACK && brother->right->color == BLACK)
            {
                brother->color = RED;
                node = node->parent;
            }
            /*     parent
                  /     \
               brother  node
           */
            else
            {
                if ((brother->right->color == RED))
                {
                    /*顺侄红转对侄红*/
                    brother->right->color = BLACK;
                    brother->color = RED;
                    leftRotate(rbtree, brother);
                    brother = node->parent->left;
                }
                /*对侄红*/
                brother->color = node->parent->color;
                node->parent->color = BLACK;
                brother->left->color = BLACK;
                rightRotate(rbtree, node->parent);
                /*退出循环*/
                node = rbtree->root;
            }
        }
    }
    node->color = BLACK;
    return ON_SUCCESS;
}
/*************************静态函数---实现函数分割线*************************/
/*红黑树初始化*/
int rbtreeInit(Rbtree **rbtree, int (*pCompare)(ELEMENTTYPE, ELEMENTTYPE), void (*print)(ELEMENTTYPE))
{
    Rbtree *tree = calloc(1, sizeof(Rbtree));
    checkRbtree(tree);
#if 0 /*根节点不分配空间，用于后续判断树是否为空*/
    tree->root = calloc(1, sizeof(RbtreeNode));
    checkRbtreeNode(tree->root);
    /*维护根节点*/
    tree->root->left == NULL;
    tree->root->right == NULL;
    tree->root->parent == NULL;

#endif
    tree->leaf = calloc(1, sizeof(RbtreeNode));
    tree->leaf->color = BLACK;
    tree->leaf->left = tree->leaf;
    tree->leaf->right = tree->leaf;
    tree->leaf->parent = tree->leaf;
    tree->leaf->val = NULL;
    tree->root = tree->leaf;
    /*维护树的节点数*/
    tree->size = 0;
    /*初始化回调函数*/
    tree->compare = pCompare;
    tree->printTree = print;

    /*解引用*/
    *rbtree = tree;
    return ON_SUCCESS;
}

/*红黑树插入*/
int rbtreeInsert(Rbtree *rbtree, ELEMENTTYPE data)
{
    checkRbtree(rbtree);
    /*创建新节点*/
    RbtreeNode *newNode = calloc(1, sizeof(RbtreeNode));
    if (newNode == NULL)
    {
        return NULL_NODE;
    }

    /*维护新节点*/
    newNode->left = rbtree->leaf;
    newNode->right = rbtree->leaf;
    newNode->parent = rbtree->leaf;
    newNode->val = data;
    /*初始化结点颜色为RED*/
    newNode->color = RED;
    /*root==NULL即树为空*/
    /*如果根节点为空，那么创建的新节点作为根节点*/
    if (rbtree->root == rbtree->leaf)
    {
        rbtree->root = newNode;
    }
#if 0 /*放弃使用size判断树是否为空的方法*/
    /*判断树中是否存在根节点*/
    if (rbtree->size == 0)
    {
        /*没有根节点，新节点成为根节点*/
        rbtree->root = newNode;
    }
#endif
    else
    {
        /*有根节点，寻找新节点父位置*/
        RbtreeNode *travel = rbtree->root;
        /*parentNode记录travel的父节点位置*/
        RbtreeNode *parentNode = rbtree->leaf;
        while (travel != rbtree->leaf)
        {
            /*寻找待插入结点的父节点*/
            parentNode = travel;
            if (rbtree->compare(data, travel->val) > 0)
            {
                travel = travel->right;
            }
            else if (rbtree->compare(data, travel->val) < 0)
            {
                travel = travel->left;
            }
            else
            {
                /*如果树中已经存在待插入值，直接返回*/
                return ON_SUCCESS;
            }
        }
        /*更新插入结点的父指针*/
        newNode->parent = parentNode;
        if (rbtree->compare(newNode->val, parentNode->val) < 0)
        {
            parentNode->left = newNode;
        }
        else
        {
            parentNode->right = newNode;
        }
    }
    rbtree->size++;
    insertFixup(rbtree, newNode);
    return ON_SUCCESS;
}

/*红黑树查找*/
RbtreeNode *rbtreeSearch(Rbtree *rbtree, ELEMENTTYPE data)
{
    if (checkRbtree(rbtree) == NULL_TREE)
    {
        return rbtree->leaf;
    }

    RbtreeNode *travel = rbtree->root;
    while (travel != rbtree->leaf)
    {
        if (rbtree->compare(data, travel->val) > 0)
        {
            travel = travel->right;
        }
        else if (rbtree->compare(data, travel->val) < 0)
        {
            travel = travel->left;
        }
        else
        {
            return travel;
        }
    }
    return travel;
}

/*红黑树删除结点分为三种情况
    1.删除度为2的节点
    方法:找到度为2节点的前驱或者后继，将其替换。将要删除的度为2目标节点转化
         为删除它的前驱结点和后继结点
    2.删除度为1的节点
    方法：寻找它的祖父节点，删除父结点，连接祖父节点即可(子承父业)
    3.删除度为0的节点
    方法：直接删除*/
/*红黑树删除*/
int rbtreeRemove(Rbtree *rbtree, ELEMENTTYPE data)
{
    if (checkRbtree(rbtree) == NULL_TREE)
    {
        return NULL_TREE;
    }

    /*根据值查找节点*/
    RbtreeNode *node = rbtreeSearch(rbtree, data);
    if (node == NULL)
    {
        return INVALID_VAL;
    }
    RbtreeNode *deleteNode = rbtree->leaf;
    if (nodeDegreeIsTwo(rbtree, node))
    {
        /*如果待删结点的度为2*/

        /*这里采用前驱节点替换(前驱后继二选一)*/
        deleteNode = seekPreNode(rbtree, node);
        node->val = deleteNode->val;
    }
    else
    {
        /*度为1或者0,直接删除*/
        deleteNode = node;
    }

    RbtreeNode *child = rbtree->leaf;
    /*程序执行到这里，待删结点一定为deleteNode*/
    /*定义待删节点的孩子节点*/
    if (deleteNode->left != rbtree->leaf)
    {
        child = deleteNode->left;
    }
    else if (deleteNode->right != rbtree->leaf)
    {
        child = deleteNode->right;
    }
    /*更新孩子结点的父指针*/
    child->parent = deleteNode->parent;

    if (deleteNode->parent == rbtree->leaf)
    {
        /*如果待删结点为根节点*/
        rbtree->root = child;
    }
    /*更新待删结点的父节点的孩子指针*/
    else if (deleteNode == deleteNode->parent->left)
    {
        deleteNode->parent->left = child;
    }
    else
    {
        deleteNode->parent->right = child;
    }

    if (deleteNode->color == BLACK)
    { /*父节点为黑，子节点为红*/
        /*单个黑节点*/

        /*修复平衡只需要待删结点的位置和颜色*/
        deleteFixup(rbtree, child);
    }
    /*程序执行到这里,一定是单个红节点*/
    if (deleteNode != NULL)
    {
        free(deleteNode);
        deleteNode = NULL;
    }
    rbtree->size--;
    return ON_SUCCESS;
}

/*红黑树前序遍历(前序遍历即是按大小顺序打印)*/
int rbtreePrePrint(Rbtree *rbtree)
{
    return prePrint(rbtree, rbtree->root);
}

/*红黑树中序遍历*/
int rbtreeInorderPrint(Rbtree *rbtree)
{
    return inOrderPrint(rbtree, rbtree->root);
}

/*红黑树后序遍历*/
int rbtreePostPrint(Rbtree *rbtree)
{
    return postPrint(rbtree, rbtree->root);
}

/*红黑树层序遍历*/
/*算法：引入队列，首先将根节点入队，随后将每一个出队节点的左右孩子添加到队列中，直到队列为空*/
int rbtreeLevelPrint(Rbtree *rbtree)
{
    checkRbtree(rbtree);
    Queue *que = NULL;
    queueInit(&que);
    queuePush(que, rbtree->root);
    int count = 1;
    /*用于获取队头节点*/
    RbtreeNode *popNode = rbtree->leaf;
    while (!queueEmpty(que))
    {
        queueTop(que, (void **)&popNode);
        rbtree->printTree(popNode->val);
        queuePop(que);
        count--;
        /*将出队结点的左右孩子入队*/
        if (popNode->left != rbtree->leaf)
        {
            queuePush(que, popNode->left);
        }
        if (popNode->right != rbtree->leaf)
        {
            queuePush(que, popNode->right);
        }
        if (count == 0)
        {
            printf("\n");
            queueSize(que, &count);
        }
    }
    queueDestroy(que);
    printf("\n");
    return ON_SUCCESS;
}
/*红黑树获取高度*/
int rbtreeGetHeight(Rbtree *rbtree, int *height)
{
    /*算法，层序遍历获取高度*/
    checkRbtree(rbtree);
    Queue *que = NULL;
    queueInit(&que);
    /*记录高度*/
    int high = 0;
    /*计数,记录当前层数的节点个数*/
    int count = 1;
    queuePush(que, rbtree->root);
    RbtreeNode *popNode = rbtree->leaf;

    while (!queueEmpty(que))
    {
        queueTop(que, (void **)&popNode);
        queuePop(que);
        count--;

        if (popNode->left != rbtree->leaf)
        {
            queuePush(que, popNode->left);
        }
        if (popNode->right != rbtree->leaf)
        {
            queuePush(que, popNode->right);
        }
        /*每当当前节点数出队完成后高度+1,同时更新下一层的节点数量*/
        if (count == 0)
        {
            high++;
            queueSize(que, &count);
        }
    }
    /*解引用*/
    *height = high;
    /*销毁队列*/
    queueDestroy(que);
    return ON_SUCCESS;
}
/*红黑树销毁*/
int rbtreeDestroy(Rbtree *rbtree)
{
    if (checkRbtree(rbtree) == NULL_TREE)
    {
        return NULL_TREE;
    }
    /*采用循环删除头结点的方式销毁：测试代码健壮性*/
#if 0
    while (rbtree->root != rbtree->leaf)
    {
        rbtreeRemove(rbtree, rbtree->root->val);
    }

#endif
    /*层序遍历的方式销毁：效率最高*/
    Queue *que = NULL;
    queueInit(&que);
    queuePush(que, rbtree->root);
    RbtreeNode *popNode = NULL;
    while (!queueEmpty(que))
    {
        queueTop(que, (void **)&popNode);
        queuePop(que);
        if (popNode->left != rbtree->leaf)
        {
            queuePush(que, popNode->left);
        }
        if (popNode->right != rbtree->leaf)
        {
            queuePush(que, popNode->right);
        }
        if (popNode != NULL)
        {
            free(popNode);
            popNode = NULL;
        }
    }
    queueDestroy(que);

    if (rbtree->leaf != NULL)
    {
        free(rbtree->leaf);
        rbtree->leaf = NULL;
    }
    if (rbtree != NULL)
    {
        free(rbtree);
        rbtree = NULL;
    }
    return ON_SUCCESS;
}